package cxydmmszl.chapter08.t142;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * <li style="color: red;">Prob</li>
 * 分金条的最小花费
 * <li style="color: green;">Desc</li>
 * 给定一个正数数组 arr，arr 的累加和代表金条的总长度，arr的每个数代表金条要分成的长度。
 * 规定长度为 k 的金条分成两块，费用为 k 个铜板。返回把金条分出 arr 中的每个数字需要的最小代价。
 * <br/><br/>[要求]<br/>
 * 时间复杂度为 O(nlogn)，空间复杂度为 O(n)。
 * <li style="color: green;">Input</li>
 * 第一行一个整数 N。表示数组长度。
 * 接下来一行 N 个整数，表示 arr 数组。
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^5<br/>
 * 1⩽arr[i]⩽10^9
 * <li style="color: green;">Output</li>
 * 一个整数表示最小代价
 * <li style="color: blue;">Link</li> CD51
 *
 * @author habitplus
 * @since 2021-10-12 21:00
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] sss) {
        int n = nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        long ans = minSplitCost(arr);
        System.out.println(ans);
    }

    private static long minSplitCost(long[] arr) {
        if (arr == null || arr.length < 2) return 0;
        /*
            哈夫曼编码的应用：贪心
            每次选两个最小的数，相加后的和再重新入堆，直到剩一个数
         */

        int n = arr.length;
        // 建堆
        for (int i = 1; i < n; i++) {
            heapInsert(arr, i);
        }

        int sz = n;
        long res = 0;
        long sum;
        while (sz != 1) {
            swap(arr, 0, sz - 1);
            heapify(arr, 0, sz - 1);
            swap(arr, 0, sz - 2);
            heapify(arr, 0, sz - 2);

            sum = arr[sz - 1] + arr[sz - 2];
            res += sum;

            arr[sz - 2] = sum;
            heapInsert(arr, sz - 2);
            sz--;
        }

        return res;
    }

    private static void heapify(long[] minHeap, int p, int sz) {
        int lch = 2 * p + 1;
        int rch = 2 * p + 2;
        int minIdx = p;
        while (lch < sz) {
            if (minHeap[lch] < minHeap[minIdx]) {
                minIdx = lch;
            }

            if (rch < sz && minHeap[rch] < minHeap[minIdx]) {
                minIdx = rch;
            }

            if (minIdx == p) break;

            swap(minHeap, p, minIdx);
            p = minIdx;
            lch = 2 * p + 1;
            rch = 2 * p + 2;
        }
    }

    private static void heapInsert(long[] minHeap, int k) {
        int p;
        while (k > 0) {
            p = (k - 1) / 2;
            if (minHeap[p] > minHeap[k]) {
                swap(minHeap, p, k);
                k = p;
            } else {
                break;
            }
        }
    }

    private static void swap(long[] arr, int i, int j) {
        long t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
